Rak
Limit pamięci: 32 MB
W Bajtocji niedawno zbudowano staw, w którym mieszka żółwi. W
każdym z domków, ponumerowanych od 1 do , które się tam
znajdują, mieszka dokładnie jeden żółw.
W najbliższym czasie do Bajtocji planuje wpaść w odwiedziny rak
Wędrownik mieszkający na co dzień w Bajtomeryce. Jest on
rakiem bardzo towarzyskim i wszystkie bajtockie żółwie są
jego przyjaciółmi. Podczas swojego pobytu, Wędrownik chce się
zatrzymać w domku u jednego z nich. Tu powstaje jednak
dylemat - wktórym domku powinien mieszkać?
Wędrownika interesują przede wszystkim takie domki, z których mógłby
odwiedzać jak najwięcej przyjaciół. Mogłoby się wydawać, że
odwiedzanie przyjaciół to żaden problem, ale jednak w bajtockim
stawie jest to w pewien sposób utrudnione. Po pierwsze, aby kogoś
odwiedzić, trzeba się najpierw dostać do jego domku. Po drugie,
trzeba później wrócić z powrotem. Zakładamy również, że Wędrowiec
nie odwiedza żółwia, u którego mieszka.
Wędrowiec porusza się zgodnie z następującymi zasadami:
- Między domkami może się przemieszczać jedynie po wyznaczonych
trasach.
- Każda z tras jest jednokierunkowa i łączy dwa różne domki.
Może istnieć kilka tras łączących te same domki.
- Rak może się poruszać na dwa sposoby -
normalnie lub wspak. Jeśli w danym momencie rak
porusza się normalnie i znajduje się w domku , to może przejść do
domku , jeśli istnieje trasa prowadząca z do . Jeśli
porusza się wspak, to może przejść z do tylko po trasie
prowadzącej z do .
- Niektóre trasy są specjalne. Jeśli rak przejdzie taką
trasą, to zaraz po tym rak zmienia swój sposób poruszania - jeśli
chodził normalnie, to odtąd chodzi wspak, a jeśli chodził wspak, to
będzie chodził normalnie. Rak nie może zmieniać sposobu poruszania się
nigdzie indziej.
- Idąc w odwiedziny, Wędrownik wychodzi ze swojego miejsca
zamieszkania, poruszając się wspak. W czasie pobytu u przyjaciela
rak nie zmienia swojego sposobu poruszania się.
W momencie powrotu do domu Wędrownik musi się poruszać wspak
(jeśli ostatnia trasa jest specjalna, to przed wejściem na nią
powinien był poruszać się normalnie).
Zadanie
Napisz program, który:
- wczyta ze standardowego wejścia opis tras łączących domki
w bajtockim stawie,
- dla każdego domku obliczy ilość przyjaciół, których mógłby
odwiedzać Wędrowiec, gdyby zamieszkał w tym domku,
- wypisze wynik na standardowe wyjście.
Wejście
W pierwszym wierszu standardowego wejścia znajdują się dwie liczby
całkowite i (,
),
oznaczające odpowiednio ilość domków i ilość tras. W
kolejnych wierszach znajdują się opisy poszczególnych tras, po
jednym w każdym wierszu. Opis trasy składa się z trzech liczb ,
i (, ). Liczba to
numer domku, w którym trasa się zaczyna, to numer domku, w
którym się kończy. Trasa jest specjalna, jeśli .
Wyjście
Twój program powinien wypisać na standardowe wyjście dokładnie
wierszy. W -tym z nich powinna się znaleźć liczba przyjaciół,
których mógłby odwiedzić Wędrowiec, gdyby mieszkał w domku numer .
Przykład
Dla danych wejściowych:
5 5
2 1 1
2 3 0
3 4 0
4 2 0
5 3 1
poprawną odpowiedzią jest:
3
3
3
3
0
Mieszkając w domku numer 1, rak może odwiedzić przyjaciół w domkach
2, 3, 4.
Mieszkając w domku numer 2, rak może odwiedzić przyjaciół w domkach
3, 4, 5.
Mieszkając w domku numer 3, rak może odwiedzić przyjaciół w domkach
2, 4, 5.
Mieszkając w domku numer 4, rak może odwiedzić przyjaciół w domkach
2, 3, 5.
Mieszkając w domku numer 5, rak nie może odwiedzić żadnego
przyjaciela.
Autor zadania: Szymon Acedański.